package ClassicDataStructuresAndAlgorithms.ClassicLinkedListAlgorithms;

public class Solution378 {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0];
        int right = matrix[n-1][n-1];


        while(left < right){
            int mid =left+ ((left-right)>>>1);
            if (check(matrix,mid,k)){
                right = mid;
            }else{
                left = mid+1;
            }
        }

        return left;
    }

    public boolean check(int[][] matrix,int mid,int k){
        int i = matrix.length-1;
        int j = 0;
        int count = 0;

        while(j< matrix.length && i>=0){
            if (matrix[i][j] <= mid){
                count=count+i+1;
                j++;
            }else {
                i--;
            }
        }

        return count>=k;
    }
}
